Search for: All records

Locomotion on dynamic rigid surface (i.e., rigid surface accelerating in an inertial frame) presents complex challenges for controller design, which are essential to address for deploying humanoid robots in dynamic real-world environments such as moving trains, ships, and airplanes. This paper introduces a real-time, provably stabilizing control approach for humanoid walking on periodically swaying rigid surface. The first key contribution is an analytical extension of the classical angular momentum-based linear inverted pendulum model from static to swaying grounds whose motion period may be different than the robot’s gait period. This extension results in a time-varying, nonhomogeneous robot model, which is fundamentally different from the existing pendulum models. We synthesize a discrete footstep control law for the model and derive a new set of sufficient stability conditions that verify the controller’s stabilizing effect. Finally, experiments conducted on a Digit humanoid robot, both in simulations and on hardware, demonstrate the framework’s effectiveness in addressing bipedal locomotion on swaying ground, even under uncertain surface motions and unknown external pushes. 

Achieving stable bipedal walking on surfaces with unknown motion remains a challenging control problem due to the hybrid, time-varying, partially unknown dynamics of the robot and the difficulty of accurate state and surface motion estimation. Surface motion imposes uncertainty on both system parameters and non-homogeneous disturbance in the walking robot dynamics. In this paper, we design an adaptive ankle torque controller to simultaneously address these two uncertainties and propose a step-length planner to minimize the required control torque. Typically, an adaptive controller is used for a continuous system. To apply adaptive control on a hybrid system such as a walking robot, an intermediate command profile is introduced to ensure a continuous error system. Simulations on a planar bipedal robot, along with comparisons against a baseline controller, demonstrate that the proposed approach effectively ensures stable walking and accurate tracking under unknown, time-varying disturbances. 

This paper proposes efficient solutions for k-core decomposition with high parallelism. The problem of k-core decomposition is fundamental in graph analysis and has applications across various domains. However, existing algorithms face significant challenges in achieving work-efficiency in theory and/or high parallelism in practice, and suffer from various performance bottlenecks. We present a simple, work-efficient parallel framework for k-core decomposition that is easy to implement and adaptable to various strategies for improving work-efficiency. We introduce two techniques to enhance parallelism: a sampling scheme to reduce contention on high-degree vertices, and vertical granularity control (VGC) to mitigate scheduling overhead for low-degree vertices. Furthermore, we design a hierarchical bucket structure to optimize performance for graphs with high coreness values. We evaluate our algorithm on a diverse set of real-world and synthetic graphs. Compared to state-of-the-art parallel algorithms, including ParK, PKC, and Julienne, our approach demonstrates superior performance on 23 out of 25 graphs when tested on a 96-core machine. Our algorithm shows speedups of up to 315× over ParK, 33.4× over PKC, and 52.5× over Julienne. 

This article presents an invariant extended Kalman filter (InEKF) approach for estimating the relative pose and linear velocity of ground robots—either legged or wheeled—using an inertial measurement unit (IMU) attached to the robot, encoders, and an external IMU placed on the moving ground. The approach explicitly accounts for ground motion in noninertial environments, such as ships or airplanes, where the ground rotates or accelerates in the inertial frame. Unlike previous methods, it does not rely on known ground pose. This consideration introduces complexity due to the nonlinear dynamics and kinematics of the reference frame. Despite this complexity, the proposed filter, based on the InEKF methodology, includes a process model that partially satisfies the group affine condition. The leg odometry-based measurement model meets the right-invariant observation form for deterministic scenarios, though the wheel odometry model does not. Observability analysis demonstrates that all state variables are observable during a broad range of ground motions, overcoming the partial observability limitations of previous filters. Experiments on a Digit humanoid robot and a Jackal wheeled robot verify the filter’s effectiveness across various ground motions. 

The kd-tree is one of the most widely used data structures to manage multi-dimensional data. Due to the ever-growing data volume, it is imperative to consider parallelism in kd-trees. However, we observed challenges in existing parallel kd-tree implementations, for both constructions and updates. The goal of this paper is to develop efficient in-memory kd-trees by supporting high parallelism and cache-efficiency. We propose the Pkd-tree (Parallel kd-tree), a parallel kd-tree that is efficient both in theory and in practice. The Pkd-tree supports parallel tree construction, batch update (insertion and deletion), and various queries including k-nearest neighbor search, range query, and range count. We proved that our algorithms have strong theoretical bounds in work (sequential time complexity), span (parallelism), and cache complexity. Our key techniques include 1) an efficient construction algorithm that optimizes work, span, and cache complexity simultaneously, and 2) reconstruction-based update algorithms that guarantee the tree to be weight-balanced. With the new algorithmic insights and careful engineering effort, we achieved a highly optimized implementation of the Pkd-tree. We tested Pkd-tree with various synthetic and real-world datasets, including both uniform and highly skewed data. We compare the Pkd-tree with state-of-the-art parallel kd-tree implementations. In all tests, with better or competitive query performance, Pkd-tree is much faster in construction and updates consistently than all baselines. We released our code. 

Abstract Accurate control of a humanoid robot's global position (i.e., its three-dimensional (3D) position in the world) is critical to the reliable execution of high-risk tasks such as avoiding collision with pedestrians in a crowded environment. This paper introduces a time-based nonlinear control approach that achieves accurate global-position tracking (GPT) for multi-domain bipedal walking. Deriving a tracking controller for bipedal robots is challenging due to the highly complex robot dynamics that are time-varying and hybrid, especially for multi-domain walking that involves multiple phases/domains of full actuation, over actuation, and underactuation. To tackle this challenge, we introduce a continuous-phase GPT control law for multi-domain walking, which provably ensures the exponential convergence of the entire error state within the full and over actuation domains and that of the directly regulated error state within the underactuation domain. We then construct sufficient multiple-Lyapunov stability conditions for the hybrid multi-domain tracking error system under the proposed GPT control law. We illustrate the proposed controller design through both three-domain walking with all motors activated and two-domain gait with inactive ankle motors. Simulations of a ROBOTIS OP3 bipedal humanoid robot demonstrate the satisfactory accuracy and convergence rate of the proposed control approach under two different cases of multi-domain walking as well as various walking speed and desired paths.